package ua.com.noobs.collections.map;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;

public class EHashMap<E, V> extends AbstractMap<E, V> {
	private static final int[] shifts = new int[10];

	private int size;
	private HashEntry<E, V>[] data;
	private int capacity;
	private int shift;
	private Set<Entry<E, V>> entrySet;

	static {
		Random random = new Random(System.currentTimeMillis());
		for (int i = 0; i < 10; i++)
			shifts[i] = 1 + 3 * i + random.nextInt(3);
	}

	public EHashMap() {
		this(4);
	}

	private void setCapacity(int size) {
		capacity = Integer.highestOneBit(4 * size);
		// noinspection unchecked
		data = new HashEntry[capacity];
	}

	public EHashMap(int maxSize) {
		setCapacity(maxSize);
		entrySet = new AbstractSet<Entry<E, V>>() {
			@Override
			public Iterator<Entry<E, V>> iterator() {
				return new Iterator<Entry<E, V>>() {
					private HashEntry<E, V> last = null;
					private HashEntry<E, V> current = null;
					private HashEntry<E, V> base = null;
					private int lastIndex = -1;
					private int index = -1;

					public boolean hasNext() {
						if (current == null) {
							for (index++; index < capacity; index++) {
								if (data[index] != null) {
									base = current = data[index];
									break;
								}
							}
						}
						return current != null;
					}

					public Entry<E, V> next() {
						if (!hasNext())
							throw new NoSuchElementException();
						last = current;
						lastIndex = index;
						current = current.next;
						if (base.next != last)
							base = base.next;
						return last;
					}

					public void remove() {
						if (last == null)
							throw new IllegalStateException();
						size--;
						if (base == last)
							data[lastIndex] = last.next;
						else
							base.next = last.next;
					}
				};
			}

			@Override
			public int size() {
				return size;
			}
		};
	}

	public EHashMap(Map<E, V> map) {
		this(map.size());
		putAll(map);
	}

	@Override
	public Set<Entry<E, V>> entrySet() {
		return entrySet;
	}

	@Override
	public void clear() {
		Arrays.fill(data, null);
		size = 0;
	}

	private int index(Object o) {
		return getHash(o.hashCode()) & (capacity - 1);
	}

	private int getHash(int h) {
		int result = h;
		for (int i : shifts)
			result ^= h >>> i;
		return result;
	}

	@Override
	public V remove(Object o) {
		if (o == null)
			return null;
		int index = index(o);
		HashEntry<E, V> current = data[index];
		HashEntry<E, V> last = null;
		while (current != null) {
			if (current.key.equals(o)) {
				if (last == null)
					data[index] = current.next;
				else
					last.next = current.next;
				size--;
				return current.value;
			}
			last = current;
			current = current.next;
		}
		return null;
	}

	@Override
	public V put(E e, V value) {
		if (e == null)
			return null;
		int index = index(e);
		HashEntry<E, V> current = data[index];
		if (current != null) {
			while (true) {
				if (current.key.equals(e)) {
					V oldValue = current.value;
					current.value = value;
					return oldValue;
				}
				if (current.next == null)
					break;
				current = current.next;
			}
		}
		if (current == null)
			data[index] = new HashEntry<E, V>(e, value);
		else
			current.next = new HashEntry<E, V>(e, value);
		size++;
		if (2 * size > capacity) {
			HashEntry<E, V>[] oldData = data;
			setCapacity(size);
			for (HashEntry<E, V> entry : oldData) {
				while (entry != null) {
					HashEntry<E, V> next = entry.next;
					index = index(entry.key);
					entry.next = data[index];
					data[index] = entry;
					entry = next;
				}
			}
		}
		return null;
	}

	@Override
	public V get(Object o) {
		if (o == null)
			return null;
		int index = index(o);
		HashEntry<E, V> current = data[index];
		while (current != null) {
			if (current.key.equals(o))
				return current.value;
			current = current.next;
		}
		return null;
	}

	@Override
	public boolean containsKey(Object o) {
		if (o == null)
			return false;
		int index = index(o);
		HashEntry<E, V> current = data[index];
		while (current != null) {
			if (current.key.equals(o))
				return true;
			current = current.next;
		}
		return false;
	}

	@Override
	public int size() {
		return size;
	}

	private static class HashEntry<E, V> implements Entry<E, V> {
		private final E key;
		private V value;
		private HashEntry<E, V> next;

		private HashEntry(E key, V value) {
			this.key = key;
			this.value = value;
		}

		public E getKey() {
			return key;
		}

		public V getValue() {
			return value;
		}

		public V setValue(V value) {
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}
	}
}